NOIP2007 普及组
T1:奖学金
题目描述
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前名学生发奖学金。期末，每个学生都有门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
这两行数据的含义是:总分最高的两个同学的学号依次是号、号。这两名同学的总分都是 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为的学生语文成绩更高一些。如果你的前两名的输出数据是:
则按输出错误处理，不能得分。
输入输出格式
输入格式：
共行。
第行为一个正整数，表示该校参加评选的学生人数。
第到行，每行有个用空格隔开的数字，每个数字都在到之间。第行的个数字依次表示学号为的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为（恰好是输入数据的行号减）。
所给的数据都是正确的，不必检验。
输出格式：
共行，每行是两个用空格隔开的正整数，依次表示前名学生的学号和总分。
输入输出样例
输入样例#1：
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
输出样例#1：
6 265
4 264
3 258
2 244
1 237
输入样例#2：
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
输出样例#2：
8 265
2 264
6 264
1 258
5 258
说明
NOIP2007普及组第一题
题解：
一道模拟题。首先，用 读入学生的语文、数学、英语三科成绩，然后用 计算总成绩，用 存储学生的编号。然后将总分从高到低进行排序，如果学号靠后的同学总成绩比学号靠前的同学的总成绩要高的话，那么交换两个学生的位置。同理，如果总成绩一样的话，再按语文成绩从高到低排序，最后，如果语文成绩也一样的话，那么学号小的同学排就在前面。
最后附上代码：
#include <cstring>
#include <iostream>
using namespace std;
int student[301][6];
void change(int i, int j) { //交换两个数组
swap(student[i][1], student[j][1]);
swap(student[i][2], student[j][2]);
swap(student[i][3], student[j][3]);
swap(student[i][4], student[j][4]);
swap(student[i][5], student[j][5]);
return;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> student[i][1] >> student[i][2] >> student[i][3]; //语文、数学、英语成绩
student[i][4] = student[i][1] + student[i][2] + student[i][3]; //总成绩
student[i][5] = i; //存储学生编号
}
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
if (student[i][4] < student[j][4]) //按总分从高到低排序
change(i, j);
else if (student[i][4] == student[j][4]) {//总分相同
if (student[i][1] < student[j][1]) //按语文成绩从高到低排序
change(i, j);
else if (student[i][1] == student[j][1] && student[i][4] > student[j][4]) //学号小的同学排在前面
change(i, j);
}
}
for (int i = 1; i <= 5; i++)
cout << student[i][5] << " " << student[i][4] << endl;
return 0;
}
T2:纪念品分组
题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入输出格式
输入格式：
共行:
第行包括一个整数，为每组纪念品价格之和的上上限。
第行为一个整数，表示购来的纪念品的总件数。
第至行每行包含一个正整数表示所对应纪念品的价格。
输出格式：
一个整数，即最少的分组数目。
输入输出样例
输入样例#1：
100
9
90
20
20
30
50
60
70
80
90
输出样例#1：
6
说明
的数据满足：
的数据满足：
NOIP2007普及组第二题
题解：
本题是一道典型的贪心问题。我们在读入物品的价格之后，对物品的价格进行排序。然后从价格最小的物品开始枚举，从价值最大的物品反向查看能否与这个物品分为一组。为什么要从价格最大的物品开始进行查看，而不是从价格最小的物品开始呢？我们可以举一个🌰。如：
我们看这个数组，当 时，在满足每组最多只能包括两件纪念品的要求下，如果从最小的物品开始配对，那么就需要分 组，这明显不是最优的。但是，从价格最大的物品开始配对时，仅需要 组就能满足要求。这便是最优的方案。
最后，我们再扫一遍这个数组，如果有物品没有被分组，那么就只能让这个物品单独一组了。所以说答案 就等于已经分的组数 没有被分组的物品的数量。
#include <iostream>
#include <algorithm>
using namespace std;
int things[30001];
bool vis[30001]; //存储这个纪念品是不是已经被选了
int main() {
int w, n; //w表每组纪念品价格之和的上上限，n表购来的纪念品的总件数
cin >> w >> n;
for (int i = 1; i <= n; i++)
cin >> things[i];
sort(things + 1, things + 1 + n); //将纪念品价格从高到低排序
int ans = 0; //一共需要分几组
for (int i = 1; i <= n; i++)
if (vis[i] != true)
for (int j = n; j > i; j--) { //在不超过w元的情况下，尽可能让每组的钱数最大
if (vis[j] != true && things[i] + things[j] <= w) {
ans++;
vis[i] = true;
vis[j] = true;
break;
}
}
for (int i = 1; i <= n; i++)
if (vis[i] != true) //有一些纪念品无法两个一组，就单独一组
ans++;
cout << ans << endl;
return 0;
}
T3:守望者的逃离
题目描述
恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在内移动，不过每次使用闪烁法术都会消耗魔法值点。守望者的魔法值恢复的速度为点，只有处在原地休息状态时才能恢复。
现在已知守望者的魔法初值，他所在的初始位置与岛的出口之间的距离，岛沉没的时间。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。
输入输出格式
输入格式：
共一行，包括空格隔开的三个非负整数。
输出格式：
共两行。
第行为字符串“”或“”（区分大小写），即守望者是否能逃离荒岛。
第行包含一个整数。第一行为“*”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“”（区分大小写）时表示守望者能走的最远距离。
输入输出样例
输入样例#1：
39 200 4
输出样例#1：
No
197
输入样例#2：
36 255 10
输出样例#2：
Yes
6
说明
的数据满足：
的数据满足：
的数据满足：
NOIP2007普及组第三题
题解：
对于本题，我们读过题目之后可以想到，这是一个动态规划问题。守望者在逃离海岛时，要么使用闪烁法术，要么跑步。因此，我们便可以考虑分别 这两种情况。
单独考虑第一种情况，我们可以想到，如果守望者的魔法值 的话，那么便使用闪烁法术，使 。而如果无法使用闪烁法术的话，那么便便令 ，然后 。
然后我们再考虑第二种情况。由于 数组目前已经有值，所以，对于第二种情况的 数组而言，要么继续保持现在的数值，要么将上一秒所能够跑的最大路程 ,我们取一个 值，便得到了。最后，统计一下答案就好辣！
附上代码：
#include <iostream>
using namespace std;
int DP[300001];
int main() {
int m, s, t; //魔法初值m，他所在的初始位置与岛的出口之间的距离s，岛沉没的时间t
cin >> m >> s >> t;
for (int i = 1; i <= t; i++) {
if (m >= 10) {
m -= 10;
DP[i] = DP[i - 1] + 60;
} else {
//如果不够减
DP[i] = DP[i - 1];
m += 4;
}
}
int maxx = 0; //守望者能走的最远距离
for (int i = 1; i <= t; i++)
DP[i] = max(DP[i], DP[i - 1] + 17);
for (int i = 1; i <= t; i++) {
if (DP[i] >= s) {
cout << "Yes" << endl;
cout << i << endl;
return 0;
}
if (DP[i] > maxx)
maxx = DP[i];
}
cout << "No" << endl;
cout << maxx << endl;
return 0;
}
T4:Hanoi 双塔问题
题目描述
给定三根足够长的细柱，在柱上放有个中间有孔的圆盘，共有个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为的情形）。
现要将这些圆盘移到柱上，在移动过程中可放在柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）三根细柱上的圆盘都要保持上小下大的顺序；
任务：设为个圆盘完成上述任务所需的最少移动次数，对于输入的，输出。
输入输出格式
输入格式：
一个正整数，表示在柱上放有个圆盘。
输出格式：
一个正整数, 为完成上述任务所需的最少移动次数。
输入输出样例
输入样例#1：
【输入样例1】
1
【输入样例2】
2
输出样例#1：
【输出样例1】
2
【输出样例2】
6
说明
【限制】
对于的数据，
对于的数据，
【提示】
设法建立与的递推关系式。
NOIP2007普及组第四题
题解：
他既然提示中说了“设法建立与的递推关系式”，我们便画画图找找规律呗。。。
如图，当 时：
这样的最小移动步数是多少呢？
无疑，直接将 柱上的两个圆盘直接移动到 柱，得到下图，这样移动次数是最少的，只需要移动两次。
我们继续考虑，当 时，
这样怎么移动呢？
我们将 柱上面两个圆盘先移动到 柱，得到下图：
（是不是这个过程与 的移动过程完全一样？
接着，我们再将 柱上的圆盘移动到 柱，再将 柱上的圆盘移动到 ，得到：
所以一共移动了 次。
我们发现，在进行 这个操作时，我们进行了两次 的操作（为什么是两次呢？是因为我们将上面的两个圆盘先移动到 柱，又移动到 柱，进行了两次 的操作），然后再加上最底下的两个圆盘直接移动到 柱的步骤，可以得到 的递推关系式。
继续验证，
| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
是不是都满足这个规律？
由于 的值是翻倍增长的，所以我们要用高精度乘法。
高精度乘法就比较常规了，每个数字乘 之后扫一遍，如果有大于或等于 的数字，则,。最后输出时注意处理一下前导 就OK辣！
#include <iostream>
using namespace std;
int Hanoi1[10001], Hanoi2[10001]; //滚动数组
int w = 1; //记录位数
void move(int i) {
if (i % 2 == 1) {
for (int i = 1; i <= w; i++) //高精度乘法
Hanoi1[i] = Hanoi2[i] * 2;
Hanoi1[1] += 2;
for (int i = 1; i <= w; i++) //高精度进位
if (Hanoi1[i] >= 10) {
Hanoi1[i + 1] += Hanoi1[i] / 10;
Hanoi1[i] = Hanoi1[i] % 10;
w++;
}
} else {
for (int i = 1; i <= w; i++) //高精度乘法
Hanoi2[i] = Hanoi1[i] * 2;
Hanoi2[1] += 2;
for (int i = 1; i <= w; i++) //高精度进位
if (Hanoi2[i] >= 10) {
Hanoi2[i + 1] += Hanoi2[i] / 10;
Hanoi2[i] = Hanoi2[i] % 10;
w++;
}
}
}
int main() {
int n;
cin >> n;
Hanoi1[1] = 2;
for (int i = 2; i <= n; i++) //上一次移动的数量 * 2 + 2
move(i);
bool tag = false; //处理前导0
for (int i = w; i >= 1; i--) {
if (n % 2 == 1) {
if(Hanoi1[i])
tag = true;
if (tag)
cout << Hanoi1[i];
} else {
if(Hanoi2[i])
tag = true;
if (tag)
cout << Hanoi2[i];
}
}
return 0;
}